package com.ming.learn.from.carl.array;

/**
 * 二分法学习
 */
public class Of20201216LeetCode35 {
    /*
    编号35：搜索插入位置
    给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
    你可以假设数组中无重复元素。
    示例 1:
    输入: [1,3,5,6], 5
    输出: 2

    示例 2:
    输入: [1,3,5,6], 2
    输出: 1

    示例 3:
    输入: [1,3,5,6], 7
    输出: 4

    示例 4:
    输入: [1,3,5,6], 0
    输出: 0
     */


    /*
    暴力解法：
    暴力解题 不一定时间消耗就非常高，关键看实现的方式，就像是二分查找时间消耗不一定就很低，是一样的。
    时间复制度：O(n)
    空间复杂度：O(1)
     */
    int searchInsert1(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            // 分别处理如下三种情况
            // 目标值在数组所有元素之前
            // 目标值等于数组中某一个元素
            // 目标值插入数组中的位置
            if (nums[i] >= target) {
                return i;
            }
        }
        // 目标值在数组所有元素之后的情况
        return nums.length;
    }

    /*
    二分法  方式一
    时间复制度：O(logn)
    空间复杂度：O(1)
     */
    int searchInsert2(int[] nums, int target) {
        int n = nums.length;
        int left = 0;
        int right = n - 1; // 定义target在左闭右闭的区间里，[left, right]
        while (left <= right) { // 当left==right，区间[left, right]依然有效
            int middle = left + ((right - left) / 2); // 防止溢出 等同于(left + right)/2
            if (nums[middle] > target) {
                right = middle - 1; // target 在左区间，所以[left, middle - 1]
            } else if (nums[middle] < target) {
                left = middle + 1;// target 在右区间，所以[middle + 1, right]
            } else {
                return middle;
            }
        }
        // 分别处理如下四种情况
        // 目标值在数组所有元素之前  [0, -1]
        // 目标值等于数组中某一个元素  return middle;
        // 目标值插入数组中的位置 [left, right]，return  right + 1
        // 目标值在数组所有元素之后的情况 [left, right]， return right + 1
        return right + 1;
    }

    /*
    二分法  方式二
    时间复制度：O(logn)
    空间复杂度：O(1)
     */
    int searchInsert3(int[] nums, int target) {
        int n = nums.length;
        int left = 0;
        int right = n; // 定义target在左闭右开的区间里，[left, right)  target
        while (left < right) { // 因为left == right的时候，在[left, right)是无效的空间
            int middle = left + ((right - left) >> 1);
            if (nums[middle] > target) {
                right = middle; // target 在左区间，在[left, middle)中
            } else if (nums[middle] < target) {
                left = middle + 1; // target 在右区间，在 [middle+1, right)中
            } else { // nums[middle] == target
                return middle; // 数组中找到目标值的情况，直接返回下标
            }
        }
        // 分别处理如下四种情况
        // 目标值在数组所有元素之前 [0,0)
        // 目标值等于数组中某一个元素 return middle
        // 目标值插入数组中的位置 [left, right) ，return right 即可
        // 目标值在数组所有元素之后的情况 [left, right)，return right 即可
        return right;
    }


    /*
    总结：
    确定要查找的区间到底是左闭右开[left, right)，还是左闭右闭[left, right]，这就是不变量。
    「二分查找的循环中，坚持循环不变量的原则」
     */
    public static void main(String[] args) {
        Of20201216LeetCode35 of20201216LeetCode35 = new Of20201216LeetCode35();
        System.out.println(of20201216LeetCode35.searchInsert3(new int[]{1, 3, 5, 6}, 0));
    }

}
